package com.wwy.arithmetic.newsuanfa;

/**
 * @author 王伟羽
 * @program: arithmetictest
 * @description: 合并有序数组
 * @create: 2025/04/02
 */

public class hebingyouxushuzu {
    /**
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
        } else {
            int i = 0;
            while (i < n) {
                int a = m + i - 1;
                while (a >= 0) {
                    if (nums2[i] < nums1[a]) {
                        nums1[a + 1] = nums1[a];
                        nums1[a] = nums2[i];
                    } else {
                        nums1[a + 1] = nums2[i];
                        break;
                    }
                    a--;
                }
                i++;
            }
        }
    }
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }


    public static void main(String[] args) {
        merge(new int[]{4, 0, 0, 0, 0, 0}, 1, new int[]{1, 2, 3, 5, 6}, 5);
    }



    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int a = m+n-1;
        int b = m-1;
        int c = n-1;
        while (b>=0&&c>=0){
            if(nums1[b]>nums2[c]){
                nums1[a--] = nums1[b--];
            }else{
                nums1[a--]=nums2[c--];
            }
        }
        while (c>=0){
            nums1[a--] = nums2[a--];
        }

    }

}
